package cn.com.yang.datastruct.graph;

/**
 * 图数据结构,无向图
 * TODO
 * @author yangyijin
 * @since 2024年2月6日-下午6:03:32
 */
public class Graph {
	//图的订单和边，边是二维矩阵或者邻接表
	private Vertex[] vertexs;
	private int[][] adjMatix;
	private int nVertex;//计数器，定点的个数
	private StackX tStackX;//深度优先搜索的栈
	private Queue tQueue;//实现广度优先搜索的队列
	private final int MAX_VERTEX=20;//最大的顶点个数
	
	public Graph() {
		vertexs = new Vertex[MAX_VERTEX];
		adjMatix = new int[MAX_VERTEX][MAX_VERTEX];
		for(int i=0;i<MAX_VERTEX;i++) {
			for(int j=0;j<MAX_VERTEX;j++) {
				adjMatix[i][j]=0;
			}
		}
		nVertex=0;
		tStackX = new StackX();
		tQueue = new Queue();
	}
	//向顶点插入数据
	public void insert(char label) {
		vertexs[nVertex++]=new Vertex(label);
	}
	//有了顶点够，更新矩阵关系
	public void addEdge(int start,int end) {
		//注意这里要更新的两个部分，倒三角
		adjMatix[start][end]=1;
		adjMatix[end][start]=1;
	}
	//打印指定顶点中的label
	public void displayVertex(int v) {
		System.out.print(vertexs[v].label);
	}  
	//实现深度优先搜索
	public void depthFirstSearch() {
		//首先访问的是第一个顶点
		//1.设置顶点的访问标志为true
		vertexs[0].isVistived=true;
		displayVertex(0);
		//2.放到栈中
		tStackX.push(0);
		while(!tStackX.isEmpty()) {
			//拿到当前栈顶的下标
			int curr = tStackX.peek();
			//感觉这个下标进一步 找当前相邻的未访问过的顶点（端点）
			//找到了就返回顶点的下标，没有返回-1
			int vpoint = getAdjUnVisit(curr);
			if(vpoint==-1) {
				//弹出栈
				tStackX.pop();
			}else {
				vertexs[vpoint].isVistived=true;
				displayVertex(vpoint);
				tStackX.push(vpoint);
			}
		}
		//搜索完毕，还原isVisitived标记
		for(int i=0;i<nVertex;i++) {
			vertexs[i].isVistived=false;
		}
	}

	/**
	 * 最下生成树，最短路径
	 */
	public void depthFirstSearchMini() {
		//首先访问的是第一个顶点
		//1.设置顶点的访问标志为true
		vertexs[0].isVistived=true;
//		displayVertex(0);
		//2.放到栈中
		tStackX.push(0);
		while(!tStackX.isEmpty()) {
			//拿到当前栈顶的下标
			int curr = tStackX.peek();
			//感觉这个下标进一步 找当前相邻的未访问过的顶点（端点）
			//找到了就返回顶点的下标，没有返回-1
			int vpoint = getAdjUnVisit(curr);
			if(vpoint==-1) {
				//弹出栈
				tStackX.pop();
			}else {
				vertexs[vpoint].isVistived=true;
				displayVertex(curr);//这里显示的是当前顶点
				displayVertex(vpoint);//这里显示的是目标顶点
				System.out.println(" ");
				tStackX.push(vpoint);
			}
		}
		//搜索完毕，还原isVisitived标记
		for(int i=0;i<nVertex;i++) {
			vertexs[i].isVistived=false;
		}
	}
	/**
	 * 返回-1，当前顶点没有未访问过的邻接顶点
	 * @param curr 当前顶点
	 * @return
	 */
	private int getAdjUnVisit(int curr) {
		//判断是不是邻接的？检索二维矩阵，是1就代表邻接
		for(int i =0;i<nVertex;i++) {
			//判断遍历到的顶点和当前的顶点是不是邻接的,
			if(adjMatix[curr][i]==1 && !vertexs[i].isVistived) {
				return i;//i就是我们要找到的邻接顶点的下标
			}
		}
		return -1;
	}
	//实现广度优先搜索
	public void breadthFirstSearch() {
		//1.访问第一个顶点
		vertexs[0].isVistived=true;
		displayVertex(0);
		//2.放入队列中
		tQueue.insert(0);//FIFO
		int v1,v2;//顶点下标
		while(!tQueue.isEmpty()) {
			v1 = tQueue.remove();//移除front节点
			while((v2=getAdjUnVisit(v1))!=-1) {
				vertexs[v2].isVistived=true;
				displayVertex(v2);
				tQueue.insert(v2);
			}
		}
		//循环结束，图搜索完毕
		for(int i=0;i<nVertex;i++) {
			vertexs[i].isVistived=false;
		}
	}
}
